package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.*;

/**
 * @author lixiaowen
 * @date 2020/9/24
 */
public class FindModeBinarySearchTree501 {
    //6ms
    static class Solution {

        public int[] findMode(TreeNode root) {
            if (root == null) return new int[0];
            Map<Integer, Integer> map = new HashMap<>();
            find(root, map);
            PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    return o2.getValue() - o1.getValue();
                }
            });

            priorityQueue.addAll(map.entrySet());
            int max = priorityQueue.peek().getValue();
            List<Integer> list = new ArrayList<>();
            while (priorityQueue.size() > 0 && priorityQueue.peek().getValue() == max) {
                list.add(priorityQueue.poll().getKey());
            }

            int[] result = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                result[i] = list.get(i);
            }
            return result;
        }

        private void find(TreeNode root, Map<Integer, Integer> map) {
            if (root == null) return;
            int val = map.getOrDefault(root.val, 0);
            map.put(root.val, val + 1);
            find(root.left, map);
            find(root.right, map);
        }
    }

    //4ms
    static class Solution2 {
        public int[] findMode(TreeNode root) {
            if (root == null) return new int[0];
            Integer pre = null;
            int cnt = 0;
            //记录当前最高频率
            int max = -1;
            //中序遍历
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> list = new ArrayList<>();
            while (stack.size() > 0 || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();

                if (pre == null) {
                    pre = root.val;
                }

                if (pre == root.val) {
                    cnt++;
                } else {
                    if (cnt > max) {
                        max = cnt;
                        list.clear();
                        list.add(pre);
                    } else if (max == cnt) {
                        list.add(pre);
                    }
                    pre = root.val;
                    cnt = 1;
                }
                root = root.right;
            }
            //最后一个元素
            if (cnt > max) {
                list.clear();
                list.add(pre);
            } else if (max == cnt) {
                list.add(pre);
            }
            int[] result = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                result[i] = list.get(i);
            }
            return result;
        }
    }

    /**
     *
     */
    //0ms
    static class Solution3 {
        int max = 1;
        int cnt = 0;
        int pre = Integer.MIN_VALUE;

        List<Integer> list = new ArrayList<>();

        public int[] findMode(TreeNode root) {
            inorder(root);
            int[] ans = new int[list.size()];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }

        public void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            if (pre == root.val) {
                cnt += 1;
            } else {
                pre = root.val;
                cnt = 1;
            }
            if (max < cnt) {
                list.clear();
                list.add(root.val);
                max = cnt;
            } else if (max == cnt) {
                list.add(root.val);
            }
            inorder(root.right);
        }

    }
}
